:: The Journal of the Institute of Internet, Broadcasting and Communication ::, Vol.24 No.1 | (2024) pp.37~42
절단 폭 최소화 문제의 최대차수 정점 분할 알고리즘
Abstract
본 논문은 NP-완전으로 최적 해를 구하는 다항시간 알고리즘이 알려져 있지 않은 절단 폭 최소화 문제에 대해 다항시간 알고리즘을 제안하였다. 주어진 그래프 G=(V,E), m=|V|, n=|E|에 대한 최소 절단 폭 CWf(G) = max v∈V CWf(v)를 찾기 위해 제안된 알고리즘은 첫 번째로, 최대차수 정점 vi를 기준으로 N G[vi] 정점들을 vi 를 통과하 는 간선수가 최소가 되도록 양분하는 열 절단면을 찾고, 좌ㆍ우의 N G[vi]들 간의 통과 간선수가 최소가 되는 행 절단면으 로 분할하였다. 두 번째로, 각 부 그래프 내부의 정점들을 선형으로 연결하고, 부 그래프들 간 간선을 연결하여 하나의 선형 배열을 만들었다. 마지막으로, 정점을 이동시켜 최소 절단폭을 갖는 최적화 과정을 수행하였다. 다양한 그래프들을 대상으로 실험한 결과, 수행 복잡도가 O(n2)인 제안된 알고리즘을 모든 데이터들에 대해 최적 해를 찾을 수 있었다.
This paper suggests polynomial time algorithm for cutwidth minimization problem that classified as NP-complete because the polynomial time algorithm to find the optimal solution has been unknown yet. To find the minimum cutwidth CWf(G) = max v∈V CWf(v) for given graph G=(V,E), m=|V|, n=|E|, the proposed algorithm divides neighborhood N G[vi] of the maximum degree vertex vi in graph G into left and right and decides the vertical cut plane with minimum number of edges pass through the vertex vi firstly. Then, we split the left and right N G[vi] into horizontal sections with minimum pass through edges. Secondly, the inner-section vertices are connected into line graph and the inter-section lines are connected by one line layout. Finally, we perform the optimization process in order to obtain the minimum cutwidth using vertex moving method. Though the proposed algorithm requires O(n2) time complexity, that can be obtains the optimal solutions for all of various experimental data
Linear layout,Cutwidth,Maximum degree,Vertical partition,Horizontal section
